#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
using namespace std;
const int N = 1e6 + 10;
int s[N];
int L[N], R[N];
bool st[N];
string str;
int n, q;
int main()
{
    std::ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    cin >> str;
    str = "0" + str;
    s[1] = str[1] == '1' ? 1 : 0;
    for (int i = 2; i <= n; i++)
    {
        if (str[i] == '1')
        {
            s[i] = s[i - 2] + 1;
        }
        else s[i] = s[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        if (str[i] == '1') L[i] = L[i - 1] + 1;
        else L[i] = 0;
    }
    for (int i = n; i >= 1; i--)
    {
        if (str[i] == '1') R[i] = R[i + 1] + 1;
        else R[i] = 0;
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        int cnt1 = L[r] + R[l];
        int cnt2 = (s[r - L[r]] - s[l + R[l]]) + (cnt1 + 1) / 2;
        int ans = len / 3 - cnt2;
        cout << max(ans, 0) << endl;
    }
    return 0;
}